/*
 * @lc app=leetcode.cn id=117 lang=javascript
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */

// 链接每层节点，返回每层头节点
// 每层看作一条链表来思考
var layer_connect = function(root) {
  if(!root) return null;
  let p = root, pre = null;
  let newHead = null; // 每层的节点
  while(p) {
    if(p.left) {
      if(pre) pre.next = p.left;
      pre = p.left;
      if(!newHead) newHead = pre;
    }

    if(p.right) {
      if(pre) pre.next = p.right;
      pre = p.right;
      if(!newHead) newHead = pre;
    }

    p = p.next;
  }
  return newHead;
}

var connect = function(root) {
    if(!root) return null;
    let p = root;
    while(p = layer_connect(p));
    return root;
};
// @lc code=end

